#include <stdio.h>
#include <stdlib.h>

int fFifoFaults ( int nMaxFrame, int nString[64], int nLen );
int fLruFaults ( int nMaxFrame, int nString[64], int nLen );

int main ()
{
	int nLen = 0, nFifoFaults = 0, nLruFaults = 0, i = 0;
	int nMaxFrame = rand () % 7;//get frame number from 1 to 7
	int nString[64];
	int bFrame = 1;
	
	printf ( "give integers ( a negative number to exit )==>\n" );

	while ( bFrame )
	{
		scanf ( "%d", &nString[i] );//get strings

		if ( nString [i] < 0 )//when negative, exit input
			bFrame = 0;
		else if ( nString [i] > 9 )//when integer is larger than 9, error
		{
			printf ( "integer error\n" );
			return 1;
		}
		else
		{
			nLen++;//count length
			i++;
		}
	}

	nFifoFaults = fFifoFaults ( nMaxFrame, nString, nLen );//calculate FIFO faults
	nLruFaults = fLruFaults ( nMaxFrame, nString, nLen );//calculate LRU faults

	printf ( "FIFO Faults = %d\n", nFifoFaults );//print FIFO faults
	printf ( "LRU Faults = %d\n", nLruFaults );//print LRU faults

	printf ( "Designed by Qisheng He (KisonHo)\nV1.0.2b\n" );
	return 0;
}

int fFifoFaults ( int nMaxFrame, int nString[64], int nLen )
{
	int nFaults = 0, nRemain = nLen, 
		i, n, nCount = 0, bFrame;
	int nFrame[nMaxFrame];//set frame

	for ( ; nRemain >= 0; nRemain-- )
	{
		n = nLen - nRemain;//get array number
		bFrame = 1;

		for ( i = 0; i < nMaxFrame && bFrame; i++ )
		{
			if ( nFrame[i] == nString[n] )//find string[i]
				bFrame = 0;//if find, set bFrame to 0
		}

		if ( bFrame )//if not find
		{
			nFrame[nCount] = nString[n];//set frame
			nCount++;//count
			if ( nCount >= nMaxFrame )//if count out of the max frame
				nCount = 0;//reset count

			nFaults++;//count faults
		}
	}

	return nFaults;
}

int fLruFaults ( int nMaxFrame, int nString[64], int nLen )
{
	int nFaults = 0, nRemain = nLen,
		i, n, bFrame, bCount;
	int nFrame[nMaxFrame];//set frame

	for ( ; nRemain >= 0; nRemain-- )
	{
		n = nLen - nRemain;//get array number
		bFrame = 1;

		if ( n >= nMaxFrame )//if n is larger than the frame
		{
			bCount = 1;
			for ( i = 0; i < nMaxFrame && bCount; i++ )
			{
				if ( nFrame[i] == nString [n+i-nMaxFrame] )//find string for longest period
					bCount = 0;
			}

			if ( bCount && ( nFrame[i-1] != nString[n] ) )//if not find
			{
				nFrame[i-1] = nString[n];//set frame
				bFrame = 0;
				nFaults++;//count faults
			}
		}
		else//else
		{
			nFrame[n] = nString[n];
			nFaults++;//count faults
		}
	}

	return nFaults;
}


